package danran.bfs;


import java.util.*;

/**
 * @Classname MinHeightTrees
 * @Description TODO
 * @Date 2021/8/28 22:02
 * @Created by ASUS
 */
public class MinHeightTrees {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        Map<Integer, List<Integer>> g = new HashMap<>();// 图结构
        // 建图
        for (int i = 0; i < n; i++) {
            g.put(i, new ArrayList<>());
        }
        for (int[] edge : edges) {
            if (edge.length == 2) {
                int start = edge[0], end = edge[1];
                addToGraph(g, start, end);
            }
        }
        // 打印图结构
        System.out.println(g);
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            List<Integer> cur = g.getOrDefault(i, new ArrayList<>());
            if (cur.size() == 1) q.offer(i);// 出度为1的放入队列中
        }
        while (!q.isEmpty()) {
            if (g.size() <= 2) break;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Integer cur = q.poll();// 出度为1的节点
                List<Integer> children = g.get(cur);// 出度为1的节点的孩子节点
                for (Integer child : children) {// 实际就只有一个孩子节点
                    List<Integer> ch = g.get(child);// 孩子节点的子节点
                    ch.remove(cur);// 删除起点
                    g.put(child, ch);// 更新终点的子节点列表
                    g.remove(cur);// 从图中删除起点（孤立的节点）
                }
            }
            // 重新统计出度为1的节点，并将其放入到队列中
            for (int i = 0; i < n; i++) {
                if (g.containsKey(i)) {
                    List<Integer> cur = g.getOrDefault(i, new ArrayList<>());
                    if (cur.size() == 1) q.offer(i);// 出度为1的放入队列中
                }
            }
        }
        return new ArrayList<>(g.keySet());
    }

    public void addToGraph(Map<Integer, List<Integer>> g, int start, int end) {
        List<Integer> t;
        if (g.containsKey(start)) t = g.get(start);
        else t = new ArrayList<>();
        t.add(end);
        g.put(start, t);
        if (g.containsKey(end)) t = g.get(end);
        else t = new ArrayList<>();
        t.add(start);
        g.put(end, t);
    }

    public static void main(String[] args) {
        System.out.println("[[0,1]]]".replace('[', '{').replace(']', '}'));
        System.out.println(new MinHeightTrees().findMinHeightTrees(1, new int[][]{{}}));
    }
}
